#pragma once

#include "generator-support.h"
#include <map>
#include <vector>

namespace cccn
{
namespace internal
{

using namespace std;

/**
 * A k-turple multi-nary counter
 *
 * The i-th element of a k-turple counter is an integer starting from 0 to some finite maximum max_i.
 * This class maintains a proper counting sequence from (0, 0, ..., 0) to (max_1-1, max_2-1, ..., , max_k-1).
 *
 */
class MultinaryCounter
  {
  public:
    MultinaryCounter ();
    /** 
     * Construct a k-tuple MultinaryCounter
     * 
     * \param max a vector of k elements, specifying the maximum of each element
     */
    MultinaryCounter (vector<uint> max);
    /// reset the k-turple counter to (0, 0, ..., 0)
    void Reset ();
    /**
     * reset the k-turple counter to (0, 0, ..., 0) and allow altering the k and
     * the maximum of each element
     *
     * \param max a vector of k elements, specifying the maximum of each element
     */
    void Reset (vector<uint> max);
    /**
     * post increment the multinary counter by 1
     *
     * \return true if the increment is done successfully; false if the value of 
     * the multinary counter is already the final sequence
     */
    bool operator++ (int);
    /**
     * Get the i-th element of the k-turple mulitnary counter
     *
     * \param i a 0-based index for retriving the i-th element of the multinary counter.
     * the i = 0 if the most significant element
     *
     * \return the i-th element
     */
    uint at (uint i) const;

  private:
    /// each proper sequence is algorithmically converted from this internal counter
    uint m_counter;

    /// the maximum value of m_counter for the given m_max
    uint m_max_counter;
    /// the weight of each element at their own i-th position
    vector<uint> m_weight;
  };

/**
 * Go through all possible combinations of reconnections
 *
 * After new vertices and edges are added to a graph, some edges have to
 * be reconnected so that degree of all vertices remain the same. However,
 * there are many possible combination of doing the reconnection, and this
 * class helps by going through all these possible combination one-by-one.
 *
 * (P.S.: This class is algorithmically correct only for odd node dgree)
 */
class ReconnectionPatternCounter_odd_k
  {
  public:
    ReconnectionPatternCounter_odd_k (const Graph& g);

    /**
     * Increment this counter to the next reconnection patten
     *
     * \return true if the increment is done successfully, false if the current
     * patten is already the final
     */
    bool NextReconnectionPattern (void);
    /**
     * Update this counter for returning the next edge for doing reconnection
     *
     * \return true if there exists an next edge; false if the current edge is
     * already the final
     */
    bool NextEdgeToReconnect (void);
    /**
     * Get the edge to reconnect
     *
     * \return a 3-tuple (u, v_old, v_new). an edge from u to v_old should be rewired
     * so that it becomes a new edge from u to v_new
     */
    vector<uint> GetEdgeToReconnect (void) const;
    /**
     * Reset this counter to the first reconnection patten
     */
    void Reset (void);
    /**
     * Return a 0-based index for the current reconnection pattern
     *
     * \return an index of the current reconnection pattern
     */
    uint GetIndex (void) const;

  private:
    typedef boost::graph_traits<BoostGraph_t>::vertex_descriptor Vertex_t;

    /// \return the maximum number of edges to reconnect
    uint GetMaxReconnectEdges () const;
    /// \return the maximum number of combination patterns for choosing v1 or v2 to reconnect
    uint GetMaxNodePatterns () const;

    /// maintain an index to each possible v1's or v2's neighbors combination patterns
    uint m_node_pattern_index;
    /// maintain an index to each possible pattern of edge reconnection
    internal::MultinaryCounter m_edge_pattern_index;
    /// maintain an index to each edge that is to be reconnected
    uint m_reconnect_edge_index;
    /** for each vertex va neighboring to v1 or v2, maintain all its neighbors va_adj
     *  where an edge between va--va_adj is reconnect to either va--v1 or va--v2
     */
    typedef map<uint, vector<uint> > ReconnectRoot_t;
    ReconnectRoot_t m_reconnect_root;

    /// expected degree for all nodes
    uint m_degree; 
    /// One of the two new vertex added to this graph
    uint m_v1;
    /// One of the two new vertex added to this graph 
    uint m_v2;

    const Graph& m_g;
    uint m_maxNodePatterns;
    uint m_index;
  };

/**
 * Return the i-th permutation pattern for a "n choose r with order" problem
 *
 * \param n total number of items
 * \param r number of items out of n are drawn
 * \param i the i-th pattern
 *
 * \return vector of k numbers
 */
vector<uint>
GetPermutationAt (const uint n, const uint r, uint i);

/**
 * Return the i-th combination pattern for a "n choose r without order" problem
 *
 * \param n total number of items
 * \param r number of items out of n are drawn
 * \param i the i-th pattern
 *
 * \return vector of k numbers
 */
vector<uint>
GetCombinationAt (const uint n, const uint r, uint i);

} // namespace internal
} // namespace cccn